When forwarding an Internet Protocol (IP) packet, a router searches a routing table according to the destination address of the IP packet. The routing table includes multiple route prefixes. Each route prefix is represented by a string made up of 0 and 1 and other symbols, such as 01*. The asterisk “*” at the end of the string indicates that the bits in this position can be any combination of 0 and 1. Each route prefix in the routing table is associated with a next hop. When a router forwards an IP packet, the router finds a corresponding prefix in the routing tabling according to the destination address of the IP packet by performing longest prefix matching. After finding the longest prefix that matches the destination address, the router forwards the IP packet according to the next hop associated with the prefix. In longest prefix matching, if a router has two route prefixes, namely, (10*→interface 1) and (1010*→interface 2), when a packet with a destination IP address 101001 is received, the address matches both prefixes while the second prefix has more matched bits, and therefore, the second prefix is regarded as the final matching result and the router forwards the packet according to the next hop associated with that prefix.
As the network scale increases, IPv6 and virtual private network (VPN) are widely used and a routing table includes more and more prefixes. A router now needs to support up to millions of route prefixes. Moreover, the interface rate of a router increases continuously, so the speed of longest prefix matching on a router needs to increase to support 40 Gbit/s, 100 Gbit/s and higher interface rates.
Conventionally, a static random access memory (SRAM) is often employed to realize high speed search but unable to support a large-sized routing table, or a dynamic random access memory (DRAM) is employed to support a large-sized routing table but unable to realize high speed search due to a low rate of the DRAM.
In order to support a large-sized routing table as well as high speed search, a trie-based method for longest prefix matching is generally adopted, where a trie is an ordered tree data structure that is used to store lots of strings. With common prefixes of strings, the storage space can be saved. The updating process is fast and the search performance is only related to the address length while unrelated to the number of prefixes. Therefore, the use of longest prefix matching based on a trie has become popular. For example, there is a method for searching the longest matched prefix by a compressed multi-bit trie in the prior art. In the case of matching based on a compressed multi-bit trie, if the step size is r bits, only r bits can be read at a time. This search speed may not satisfy the requirement of continuously growing line rates.
Therefore, a heretofore unaddressed need exists in the art to address the aforementioned deficiencies and inadequacies.